//Cracking the coding interview (5th), 2_7
//Implement a function to check if a linked list is a palindrome.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _data {
    int data;
    struct _data * next;
} DATA;

DATA* IsSymmetric (DATA *p, int L, int flag)
{
    DATA *pn;
    if (1 == L)
    {
        if (1 == flag)
        {
            pn = p->next->next;
        }
        else
        {
            pn = p->next;
        }
        if (pn->data == p->data)
        {
            if (NULL != pn->next)
            {
                return pn->next;
            }
            else
            {
                return pn;
            }
        }
        else
        {
            return NULL;
        }
    }
    else
    {
        pn = IsSymmetric (p->next, L - 1, flag);
        if (NULL != pn && pn->data == p->data)
        {
            if (NULL != pn->next)
            {
                return pn->next;
            }
            else
            {
                return pn;
            }
        }
        else
        {
            return NULL;
        }
    }
}

int IsPalindrome (DATA *p)
{
    int N;
    DATA *pp;

    if (NULL == p)
    {
        return 0;
    }
    else
    {
        N = 0;
        pp = p;
        while (pp)
        {
            N++;
            pp = pp->next;
        }
        if (1 == N)
        {
            return 1;
        }
        else
        {
            return (NULL != IsSymmetric (p, N/2, N%2));
        }
    }
}

void main ()
{
    DATA *pa, *p, *pp;

    pa = (DATA *) malloc (sizeof(DATA));

    p = pa;
    p->data = 2;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 1;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 0;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 1;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 3;
    p->next = NULL;

    printf ("%d\n", IsPalindrome(pa));

    pp = NULL;
    p = pa;
    while (p)
    {
        pp = p;
        p = p->next;
        free (pp);
    }
}
